import java.util.HashMap;

/**
 * @ClassName Offer_35
 * @Description 剑指 Offer 35. 复杂链表的复制
 * @Author clockTown
 * @Date 2021/8/13 22:19
 * @Version 1.0
 */

/*
// Definition for a Node.
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
*/

class Offer35 {
}



/**
 * v0 hashMap
 */
class Offer35V0 {
    class Node {
        int val;
        Node next;

        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }
    public Node copyRandomList(Node head) {
        Node cur = head;
        HashMap<Node, Node> map = new HashMap<>();

        //复制原始链表的节点，并建立映射关系
        while (cur != null) {
            map.put(cur, new Node(cur.val));
            cur = cur.next;
        }

        cur = head;
        while (cur != null) {
            //map.get(cur) 表示原链表节点映射的新链表的节点
            map.get(cur).next = map.get(cur.next);
            map.get(cur).random = map.get(cur.random);
            cur = cur.next;
        }
        return map.get(head);
    }
}

/**
 * v1 拼接+拆分
 */
class Offer35V1 {
    class Node {
        int val;
        Node next;

        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }
    public Node copyRandomList(Node head) {
        Node cur = head;
        //复制各节点，并构建拼接链表
        while (cur != null) {
            Node temp = new Node(cur.val);
            temp.next = cur.next;
            cur.next = temp;
            cur = temp.next;
        }

        //构建各新节点的 random 指向
        cur = head;
        while (cur != null) {
            if (cur.random != null) {
                cur.next.random = cur.random.next;
            }
            cur = cur.next;
        }

        //拆分
        cur = head.next;
        Node pre = head, res = head.next;
        while (cur.next != null) {
            pre.next = pre.next.next;
            cur.next = cur.next.next;
            pre = pre.next;
            res = res.next;
        }
        // 单独处理原链表尾节点
        res.next = null;
        // 返回新链表头节点
        return res;
    }
}